package com.kehao.leetcode.hard.tree_graph;

import com.kehao.utils.LeetCodeUtil;
import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

public class FindCircleNumSolution {
    public int findCircleNum(int[][] isConnected) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < isConnected.length; i++) {
            map.put(i,-1);
        }
        for (int i = 0; i < isConnected.length; i++) {
            for (int j = i+1; j < isConnected.length; j++) {
                if(isConnected[i][j]==1){
                    int rooti = getRoot(map, i);
                    int rootj = getRoot(map, j);
                    if(rooti!=rootj) {
                        map.put(rootj, rooti);
                    }
                }
            }
        }
        HashSet set = new HashSet();
        for (int i = 0; i < isConnected.length; i++) {
            set.add(getRoot(map,i));
        }
        return set.size();
    }
    private int getRoot(HashMap<Integer,Integer> map,int i){
        int before = i;
        int parent = map.get(i);
        while (parent!=-1){
            i = parent;
            parent = map.get(parent);
        }
        if(before!=i)map.put(before,i);
        return i;
    }

    @Test
    public void test(){
//        String s = LeetCodeUtil.bracketTransform("[[1,1,0,0,0,0,0,1,0,0,0,0,0,0,0],[1,1,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,1,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,1,0,1,1,0,0,0,0,0,0,0,0],[0,0,0,0,1,0,0,0,0,1,1,0,0,0,0],[0,0,0,1,0,1,0,0,0,0,1,0,0,0,0],[0,0,0,1,0,0,1,0,1,0,0,0,0,1,0],[1,0,0,0,0,0,0,1,1,0,0,0,0,0,0],[0,0,0,0,0,0,1,1,1,0,0,0,0,1,0],[0,0,0,0,1,0,0,0,0,1,0,1,0,0,1],[0,0,0,0,1,1,0,0,0,0,1,1,0,0,0],[0,0,0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,1,0,1,0,0,0,0,1,0],[0,0,0,0,0,0,0,0,0,1,0,0,0,0,1]]");
//        System.out.println(s);
    }


    @Test
    public void test01(){
        int[][] isConnected = {{1,1,0},{1,1,0},{0,0,1}};
        int result = findCircleNum(isConnected);
        System.out.println(result);
    }

    @Test
    public void test02(){
        int[][] isConnected = {{1,0,0},{0,1,0},{0,0,1}};
        int result = findCircleNum(isConnected);
        System.out.println(result);
    }

    @Test
    public void test03(){
        int[][] isConnected = {
                {1,1,0,0,0,0,0,1,0,0,0,0,0,0,0},
                {1,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {0,0,1,0,0,0,0,0,0,0,0,0,0,0,0},
                {0,0,0,1,0,1,1,0,0,0,0,0,0,0,0},
                {0,0,0,0,1,0,0,0,0,1,1,0,0,0,0},
                {0,0,0,1,0,1,0,0,0,0,1,0,0,0,0},
                {0,0,0,1,0,0,1,0,1,0,0,0,0,1,0},
                {1,0,0,0,0,0,0,1,1,0,0,0,0,0,0},
                {0,0,0,0,0,0,1,1,1,0,0,0,0,1,0},
                {0,0,0,0,1,0,0,0,0,1,0,1,0,0,1},
                {0,0,0,0,1,1,0,0,0,0,1,1,0,0,0},
                {0,0,0,0,0,0,0,0,0,1,1,1,0,0,0},
                {0,0,0,0,0,0,0,0,0,0,0,0,1,0,0},
                {0,0,0,0,0,0,1,0,1,0,0,0,0,1,0},
                {0,0,0,0,0,0,0,0,0,1,0,0,0,0,1}};
        int result = findCircleNum(isConnected);
        System.out.println(result);
    }

}
